from typing import List
### 双指针法：
# 4. 238. 把数组里的0全部移动到数组末尾: 要求原地修改，并且保留原本的正数的顺序
class MoveZeroes:
    def solution1(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 首尾指针不行：
        # 考虑快慢指针：
        # 从尾部开始，一个指针找非0的值，一个找0，直到找不到0为止：这个方案无法保证原来的顺序
        slow,fast=len(nums)-1,len(nums)-1
        while fast >=0:
            if nums[fast]!=0:
                fast-=1
                continue
            if nums[slow]==0:
                slow-=1
                continue
            temp=nums[slow]
            nums[slow]=nums[fast]
            nums[fast]=temp
        # return nums
    def solution(self,nums:List[int]):
        # 快慢指针：一个快指针在前面找非0的值
        slow,fast=0,0
        while fast<len(nums):
            if nums[fast]!=0:
                nums[slow]=nums[fast] # 原地复写 ⭐
                slow+=1
            fast+=1
        for i in range(slow,len(nums)): # 把fast不满足条件之后的都置为0
            nums[i]=0
        return nums
    def test(self):
        nums=[1,0,2,3,0,0,4]
        print(self.solution(nums))

# 5. 11 盛最多水的容器
# 中等
# 相关标签
# premium lock icon
# 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
# 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
# 返回容器可以储存的最大水量。
# 说明：你不能倾斜容器。
# 分析：即求解x*min(y1,y2)的最大值 ？和双指针法有什么关系？ -> 相向指针：又有点像脑经急转弯了
# 应用时，每次移动y值更小的那一个指针：数学逻辑证明：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
class MaxArea:
    def solution(self, height: List[int]) -> int:
        left,right=0,len(height)-1
        maxarea=0
        while left<right:
            area=(right-left)*min(height[left],height[right])
            maxarea=max(maxarea,area)
            if height[left]<height[right]:
                left+=1
            else:
                right-=1
        return maxarea
    def test(self):
        height = [1,8,6,2,5,4,8,3,7]
        print(self.solution(height))

# 6. 找数组里3个和为0的三个数。返回的元组不带重复的组合。
# 算法流程：
# 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
# 对数组进行排序。
# 遍历排序后数组：
# 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
# 对于重复元素：跳过，避免出现重复解
# 令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
# 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
# 若和大于 0，说明 nums[R] 太大，R 左移
# 若和小于 0，说明 nums[L] 太小，L 右移
class ThreeSum:
    def solution(self, nums: List[int]) -> List[List[int]]:
        # 先排序：
        sorted_nums = sorted(nums)
        res=[]
        n=len(nums)
        if (not nums or n < 3):
            return []
        for i in range(n):
            if sorted_nums[i]>0:
                break
            print(sorted_nums[i],sorted_nums[i-1])
            if i>0 and sorted_nums[i]==sorted_nums[i-1]: # 重复的target不进行统计，从第二个元素才开始考虑重复的的
                continue
            L=i+1
            R=n-1
            while L<R:
                if sorted_nums[L]+sorted_nums[R]+sorted_nums[i]==0:
                    res.append([sorted_nums[L],sorted_nums[R],sorted_nums[i]])
                    # ⭐ 如何避免取到重复的组合？
                    while L<R and sorted_nums[L]==sorted_nums[L+1]: # ! python处理逻辑语句时也是有顺序的，后面的条件放前面会报错
                        L=L+1
                    while L<R and sorted_nums[R]==sorted_nums[R-1]:
                        R=R-1
                    L+=1
                    R-=1
                elif sorted_nums[L]+sorted_nums[R]+sorted_nums[i]>0:
                    R-=1
                else:
                    L+=1
            i+=1
        return res
    def test(self):
        nums=[0,0,0,0]
        print(self.solution(nums))


if __name__=='__main__':
    ThreeSum().test()